Search results for "Traveling salesman problem"
showing 5 items of 5 documents
Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm
2019
Abstract In this paper, we deal with the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. First, we prove that under special conditions the problem can be solved as an Asymmetric Traveling Salesman Problem with Time Windows, with suitable-defined time windows and (constant) travel times. Second, we show that, if the special conditions do not hold, the time-independent optimal solution provides both a lower bound and (eventually) an upper bound with a worst-case guarantee for the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. Finally, a branch-and-bound algorithm is presented and tested on a set of 4800 instances. The results have been compared…
NP-completeness of the hamming salesman problem
1985
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra
1998
[EN] In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-i…
On Randomness and Structure in Euclidean TSP Instances: A Study With Heuristic Methods
2021
Prediction of the quality of the result provided by a specific solving method is an important factor when choosing how to solve a given problem. The more accurate the prediction, the more appropriate the decision on what to choose when several solving applications are available. In this article, we study the impact of the structure of a Traveling Salesman Problem instance on the quality of the solution when using two representative heuristics: the population-based Ant Colony Optimization (ACO) and the local search Lin-Kernighan (LK) algorithm. The quality of the result for a solving method is measured by the computation accuracy, which is expressed using the percent error between its soluti…
Intrinsic Lipschitz Graphs and Vertical β-Numbers in the Heisenberg Group
2016
The purpose of this paper is to introduce and study some basic concepts of quantitative rectifiability in the first Heisenberg group $\mathbb{H}$. In particular, we aim to demonstrate that new phenomena arise compared to the Euclidean theory, founded by G. David and S. Semmes in the 90's. The theory in $\mathbb{H}$ has an apparent connection to certain nonlinear PDEs, which do not play a role with similar questions in $\mathbb{R}^{3}$. Our main object of study are the intrinsic Lipschitz graphs in $\mathbb{H}$, introduced by B. Franchi, R. Serapioni and F. Serra Cassano in 2006. We claim that these $3$-dimensional sets in $\mathbb{H}$, if any, deserve to be called quantitatively $3$-rectifi…